package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/10/8 10:33
 * @Description: 验证二分搜索树
 */
public class Num98_IsValidBST {
    /**
     * 错误解法，这种无法保证左子树的所有节点都小于根节点
     * 右子树的所有节点都大于根节点,如下，下图这个二叉树就会被判true
     *       5
            / \
     *    4   6
     *       / \
     *      3   7
     * @param root
     * @return
     */
//    public boolean isValidBST(TreeNode root) {
//        // base case
//        if (root == null) {
//            return true;
//        }
//        if (root.left != null && root.left.val > root.val) {
//            return false;
//        }
//        if (root.right != null && root.right.val < root.val) {
//            return false;
//        }
//        return isValidBST(root.left) && isValidBST(root.right);
//    }

    /**
     * 对于任意一颗BST，都满足左子树的所有节点 < 根节点 < 右子树的所有节点
     * 因此需要将root的信息传递给所有子树
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root,null,null);
    }

    /**
     * 默认当前root是左子树的最大值，右子树的最小值
     * @param root 当前树
     * @param min 从父树传来的最小值
     * @param max 从父树传来的最大值
     * @return
     */
    private boolean isValidBSTHelper(TreeNode root, TreeNode min, TreeNode max) {
        // base case
        if (root == null) {
            return true;
        }
        // 反例
        if (min != null && min.val >= root.val) return false;
        if (max != null && max.val <= root.val) return false;
        return isValidBSTHelper(root.left,min,root) && isValidBSTHelper(root.right,root,max);
    }
}
